1. Field of the Invention
This invention is applicable to the arithmetic-logic unit (ALU) or that functional part of a digital computer that carries out arithmetic and logic operations on operands. More particularly the invention is directed to a parsing technique for arranging the input information received by the ALU, which consists of operands, operation codes, and format codes.
2. Description of Prior Art
In the process of compilation into machine executable code of a program written in a high-level language, the procedure for examining arithmetic expressions and determining operator precedence, the order of execution of the operators, is often referred to as the arithmetic scan. Since syntactically correct arithmetic expressions are well formed in that they possess regular properties related to the operands and the operators, many specialized parsing or scanning techniques have been developed.
Although it is algebraically well defined, an arithmetic expression is not computationally well defined unless the precise order of arithmetic operations is specified. The specification of ordering can be exhibited by a computation tree, by a fully parenthesized statement or by a Polish form such as Polish prefix notation.
One possible, but impractical, technique is to require the programmer to write arithmetic expressions in fully parenthesized notation (i.e., parentheses must be placed around each pair of operands and its associated operator) to obviate the need for knowledge about the relationships between operators in determining the order in which the operations are to be performed.
Most commonly used are transformational systems, which convert the normal infix form (i.e., the form in which the operator is placed between its operands) to a Polish form, in which there exist no parentheses and the order of execution of the operators is specified by their positioning. Such a system is needed because of the difficulty of associating operands with operators in infix notation.
Polish notation was originally developed in the prefix form, in which the operators precede the operands.
The postfix or suffix form, also known as reverse Polish notation or RPN, which is logically equivalent to the prefix form, has been widely used in computing. Many compilers first transform an arithmetic expression from its ordinary or infix form into RPN, so that its evaluation can be done in a single left-to-right scan.
The usual approach for parsing arithmetic expressions is to make a one pass scan over the string of characters, operands and operations, to transform them into a Polish form by using single operand stack and operator stacks. An implicit assumption is made that these Polish strings are to be operated upon by a computing system that permits only one arithmetic operation to be performed at any given time. For example, the arithmetic expression EQU "Z=A+B+C+D"
would be transformed into the Polish prefix string EQU "Z.rarw.+++ABCD"
which defines the computation tree 10 shown in FIG. 1.
The operator precedence is not pre determined and no operational subgroupings or associations are pre defined. Hence, this parsed expression may only be operated upon sequentially, e.g., by a one processor.